#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 076. 最小覆盖子串.py
@time: 2022/1/16 15:16
@desc: https://leetcode-cn.com/problems/minimum-window-substring/
> 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
    注意：
        - 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
        - 如果 s 中存在这样的子串，我们保证它是唯一的答案。

@解题思路：
    1. 滑动窗口（左右指针）
    2. 可以用哈希表来检查是否满足目标字符串t的要求
    3. crazy
    4. Ot(C⋅∣s∣+∣t∣), Qs(C)
'''


class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """

        def check():
            """
            检查目前的窗口是否满足了字符串t的要求
            思路：检查目前cnt里所有的k, v是否满足ori的k, v需求
            """
            for k, v in ori.items():
                # 一旦当前窗口中字母出现的频率与字符串t的频率不匹配就返回False
                if cnt.get(k, 0) < v:
                    return False
            return True

        # 分别统计字符串t和字符串s中窗口的字母频率
        ori, cnt = {}, {}

        # 统计字符串t的频率，用get方法设默认值（记不住collections）
        for _t in t:
            count = ori.get(_t, 0) + 1
            ori[_t] = count

        tlen, slen = len(t), len(s)

        # 窗口长度，目标窗口左边界，目标窗口有边界
        win_len, ans_left, ans_right = 2 ** 31, -1, -1

        # 左右指针
        left, right = 0, -1

        while right < slen:
            # 右指针滑动
            right += 1
            if right < slen and s[right] in ori:
                cnt[s[right]] = cnt.get(s[right], 0) + 1
            # 当目前窗口满足了字符串t，就滑动左区间
            while check() and left <= right:
                if right - left + 1 < win_len:
                    # 一旦出现更小的窗口，就更新窗口大小
                    win_len = right - left + 1
                    ans_left = left
                    ans_right = left + win_len

                # 移动左指针，也就是缩小窗口，并更新cnt（因为窗口去掉了左指针上的元素）, 此后check() 会检查是否还满足匹配要求
                # 当check（）发现已经不满足了，那么事实上也没有必要继续滑动左指针了，因此跳出当前循环，滑动有比右指针，继续检查新的窗口
                if s[left] in ori:
                    cnt[s[left]] = cnt.get(s[left], 0) - 1
                left += 1

        return s[ans_left: ans_right] if ans_left != -1 else ''



